package demo1;

/**
 * @ClassName HashBucket
 * @Description 哈希桶
 * @Author ZJX
 * @Date 2024/8/7 14:56
 * @Version 1.0
 */

public class HashBucket {
    static class Node{
        public String key;
        public int val;
        public Node next;

        public Node(String key, int val) {
            this.key = key;
            this.val = val;
        }

    }

    public Node[] array;
    public int usedSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子

    public HashBucket(){
        array = new Node[10];
    }

    // 哈希函数
    private int hashFunc(String key, int capacity) {
        return Math.abs(key.hashCode() % capacity);
    }

    /*
     * @param key:
    	 * @param val:
      * @return void
     * @author: ZJX
     * @description:  哈希桶的插入元素
     * @date: 2024/8/7 15:03
     */
    public void put(String key, int val) {
        int index = hashFunc(key,array.length); // 利用哈希函数计算出数组下标
        Node cur = array[index]; // 获取索引位置的头节点

        while(cur != null){
            if (cur.key.equals(key)){
//                找到相同的键  更新其值
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

//        如果没有找到 头插法插入其值
        Node newNode = new Node(key,val);
        newNode.next = array[index];
        array[index] = newNode;
        usedSize++;

        if (doLoadFactor() > DEFAULT_LOAD_FACTOR){
//            大于负载因子 要扩容 ! !
            resize(); // 扩容操作
        }
    }

//    扩容
    private void resize() {
        int newCapacity = array.length * 2;
        Node[] newArray = new Node[newCapacity]; // 二倍扩容 创建新的数组

//        遍历旧数组 将其所有键值对 重新利用哈希函数存放到新哈希表里面
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur != null){
                Node next = cur.next; // 保存当前节点的下一个节点

                int newIndex = hashFunc(cur.key,newCapacity); // 重新计算哈希值和索引位置

//             头插法插入到新数组中
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;

                cur = next;
            }
        }
        array = newArray;
    }

//    计算当前 负载因子
    private float doLoadFactor(){
        return (float) usedSize / array.length;
    }

//    在哈希表中查找并返回与指定键 (key) 关联的值
    public int get(String key){
        int index = hashFunc(key,array.length);
        Node cur = array[index];

        while(cur != null){
            if (cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1; // 没找到
    }
}
